package com.hyb.algorithm.data.struct.stack;

import com.hyb.algorithm.data.struct.tree.TreeNode;

import java.util.*;

/**
 * 作者：力扣官方题解
 * 链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author: ybhu
 * @create: 2023/12/20 18:29
 */
public class InorderTraversal {


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }


    private class Command {
        String s;
        TreeNode node;

        public Command(String s, TreeNode node) {
            this.s = s;
            this.node = node;
        }
    }


    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();

        Stack<Command> stack = new Stack<>();

        stack.push(new Command("go", root));

        while (!stack.isEmpty()) {

            Command command = stack.pop();

            if (command.s.equals("print")) {
                res.add(command.node.val);
            } else {
                if(command.node==null){
                    continue;
                }

                if (command.node.right != null) {
                    stack.push(new Command("go", command.node.right));
                }


                stack.push(new Command("print", command.node));


                if (command.node.left != null) {
                    stack.push(new Command("go", command.node.left));
                }
            }
        }

        return res;
    }


}
